package multipleMergeSort

import "SearchEngine/index/getTmpIndexs"

type index = getTmpIndexs.TmpIndex //类型别名

// 归并排序，自顶向下归并
func MergeSort(nums []index) []index {
	lens := len(nums)
	if lens < 2 {
		return nums
	}
	middle := lens / 2
	return merge(MergeSort(nums[0:middle]), MergeSort(nums[middle:]))
}

func merge(left []index, right []index) []index {
	var result []index
	for len(left) != 0 && len(right) != 0 {
		if left[0].TermID <= right[0].TermID {
			result = append(result, left[0])
			left = left[1:] //改变切片起始位置，从而不用改变归并的下标
		} else {
			result = append(result, right[0])
			right = right[1:]
		}
	}

	if len(left) != 0 {
		result = append(result, left...)
	}

	if len(right) != 0 {
		result = append(result, right...)
	}

	return result
}
